|
The secretary problem is one of many names for a famous problem of the optimal stopping theory. The problem has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem. The basic form of the problem is the following: imagine an administrator willing to hire the best secretary out of rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant. If the decision can be deferred to the end, this can be solved by the simple maximum selection algorithm of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be made immediately. The problem has an elegant solution. The optimal stopping rule prescribes always rejecting the first applicants after the interview (where ''e'' is the base of the natural logarithm) and then stopping at the first applicant who is better than every applicant interviewed so far (or continuing to the last applicant if this never occurs). Sometimes this strategy is called the stopping rule, because the probability of stopping at the best applicant with this strategy is about already for moderate values of . One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple and selects the single best candidate about 37% of the time, irrespective of whether there are 100 or 100 million applicants. In fact, for any value of the probability of selecting the best candidate when using the optimal policy is at least . ==Formulation== Although there are many variations, the basic problem can be stated as follows: * There is a single position to fill. * There are ''n'' applicants for the position, and the value of ''n'' is known. * The applicants, if seen altogether, can be ranked from best to worst unambiguously. * The applicants are interviewed sequentially in random order, with each order being equally likely. * Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable. * The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far. * The objective of the general solution is to have the highest probability of selecting the best applicant of the whole group. This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant and zero otherwise. Terminology: A ''candidate'' is defined as an applicant who, when interviewed, is better than all the applicants interviewed previously. ''Skip'' is used to mean "reject immediately after the interview". Clearly, since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. The "candidate" in this context corresponds to the concept of record in permutation. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「secretary problem」の詳細全文を読む スポンサード リンク
|